/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 字符串交替 判断字符串s3是否由s1和s2组成，字符保持原有的相对顺序
 * 
 * s1 = "aabcc", s2 = "dbbca", When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return
 * false.
 * 
 * s1=abc s2 = def s3=adbecf true s3=abcdee false
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class InterleavingString {

    public boolean isInterleave(String s1, String s2, String s3) {
            int m = s1.length();
           int n = s2.length();
           int s = s3.length();
           // 如果长度不一致
           if (s != m + n) {
               return false;
           }
           boolean[][] dp = new boolean[n + 1][m + 1];
           dp[0][0] = true;

           for (int i = 0; i < n + 1; i++) {
               for (int j = 0; j < m + 1; j++) {
                   if (dp[i][j] || (i - 1 >= 0 && dp[i - 1][j]
                           && s2.charAt(i - 1) == s3.charAt(i + j - 1)) || (j-1>=0 && dp[i][j - 1]
                           && s1.charAt(j - 1) == s3.charAt(i + j - 1))) {
                       dp[i][j] = true;
                   } else {
                       dp[i][j] = false;
                   }
               }
           }
           return dp[n][m];
       }
}
